|
Verifiable computing (or verified computation or verified computing) is enabling a computer to offload the computation of some function, to other perhaps untrusted clients, while maintaining verifiable results. The other clients evaluate the function and return the result with a proof that the computation of the function was carried out correctly. The introduction of this notion came as a result of the increasingly common phenomenon of "outsourcing" computation to untrusted users in projects such as SETI@home and also to the growing desire of weak clients to outsource computational tasks to a more powerful computation service like in Cloud computing. The term ''verifiable computing'' was formalized by Rosario Gennaro, Craig Gentry, and Bryan Parno.〔 〕 ==Motivation and overview== The growing desire to outsource computational tasks from a relatively weak computational device (client) to a more powerful computation services (worker), and the problem of dishonest workers who modify their client’s software to return plausible results without performing the actual work 〔 〕 motivated the formalization of the notion of Verifiable Computation.〔 Verifiable computing is not only concerned with getting the result of the outsourced function on the client’s input and the proof of its correctness, but also with the client being able to verify the proof with significantly less computational effort than computing the function from scratch. Considerable attention has been devoted to verifying the computation of functions performed by untrusted workers including the use of secure coprocessors,〔 〕〔 〕 Trusted Platform Modules (TPMs),〔 〕 interactive proofs,〔L. Babai (1985). "Trading group theory for randomness." In ''Proceedings of the ACM Symposium on Theory of Computing (STOC)'', New York, NY, USA, pp. 421–429〕〔S. Goldwasser, S. Micali, and C. Rackoff (1989). "The knowledge complexity of interactive proof-systems." ''SIAM Journal on Computing'', 18(1), pp. 186–208〕 probabilistically checkable proofs,〔S. Arora and S. Safra (1998). "Probabilistically checkable proofs: a new characterization of NP." ''Journal of the ACM'', 45, pp.501-555〕〔O. Goldreich (1998). ''Modern Cryptography, Probabilistic Proofs and Pseudorandomness.'' Algorithms and Combinatorics series, 17, Springer〕 efficient arguments,〔J. Kilian (1992). "A note on efficient zero-knowledge proofs and arguments (extended abstract)." In ''Proceedings of the ACM Symposium on Theory of Computing (STOC)''〕〔J. Kilian (1995). "Improved efficient arguments (preliminary version)." In ''Proceedings of Crypto'', London, UK, pp. 311–324. Springer-Verlag〕 and Micali’s CS proofs.〔S. Micali (1994). "CS proofs (extended abstract)." In ''Proceedings of the IEEE Symposium on Foundations of Computer Science'', pp. 436-453.〕 These verifications are either interactive which require the client to interact with the worker to verify the correctness proof,〔〔 or are non-interactive protocols which can be proven in the random oracle model.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Verifiable computing」の詳細全文を読む スポンサード リンク
|